import java.awt.Color; 

import javax.swing.JLabel;
import javax.swing.JPanel;


@SuppressWarnings("serial")
public class ArvoreSplay extends JPanel {
	
	
	
	Node root;
	JLabel buscado; // Mostra o Elemento que foi Procurado
	final int DELTA = 200;
	public int painel_width; 
	
	public ArvoreSplay(int n) {
		//Cor do BackGround
		setBackground(Color.WHITE);
		// seta o Layout da Classe
		setLayout(null);	
		root = null;
		painel_width = n; // recebe o tamanho do painel arvores.
		buscado = new JLabel ("Elemento buscado: ");
		add (buscado);
		buscado.setVisible(true);
	}
	
	/********************************************************************************************************
	 **************************************FUNÇÃO ALTURA ****************************************************
	 ********************************************************************************************************/
	public int altura(Node aux) {
		if(aux == null)
			return -1;
		int h_esquerda = 0;
		int h_direita = 0;
		if(aux.esquerdo == null && aux.direito == null)
			return 0;
		h_esquerda = altura(aux.esquerdo);
		h_direita = altura(aux.direito);
		
		if(h_esquerda > h_direita)
			return h_esquerda + 1;
		else
			return h_direita + 1;
	}
	/********************************************************************************************************
	 **************************************FUNÇÕES DE ROTAÇÃO************************************************
	 ********************************************************************************************************/
	
	/*
	 *  ============= Zig ===============
	 */
	public void zig (Node aux) {
		Node pai = aux.pai.pai; // Guarda o avô do auxiliar
		Node vitima = aux.pai; // O elemento que será colocado abaixo de aux 
		if(aux.pai != root) {
			if(aux.pai == pai.esquerdo) {
				pai.esquerdo = aux;
				aux.pai = pai;
				
				vitima.esquerdo = aux.direito;
				if(vitima.esquerdo != null)
					vitima.esquerdo.pai = vitima;
				
				aux.direito = vitima;
				vitima.pai = aux;		
				
			} else {
				pai.direito = aux;
				aux.pai = pai;
				
				vitima.esquerdo = aux.direito;
				if(vitima.esquerdo != null)
					vitima.esquerdo.pai = vitima;
				
				aux.direito = vitima;
				vitima.pai = aux;							
			}			
		}
		// Se o pai de aux for raiz...
		else {
			root = aux;
			aux.pai = pai; // null
			
			vitima.esquerdo = aux.direito;
			if(vitima.esquerdo != null)
				vitima.esquerdo.pai = vitima;
			
			aux.direito = vitima;
			vitima.pai = aux;
		}
	} // Zig

	/*
	 *  ============= Zag ===============
	 */
	public void zag (Node aux) {
		Node pai = aux.pai.pai; // Guarda o avô do auxiliar
		Node vitima = aux.pai; // O elemento que será colocado abaixo de aux 
		if(aux.pai != root) {
			if(aux.pai == pai.esquerdo) {
				pai.esquerdo = aux;
				aux.pai = pai;
				
				vitima.direito = aux.esquerdo;
				if(vitima.direito != null)
					vitima.direito.pai = vitima;
				
				aux.esquerdo = vitima;
				vitima.pai = aux;		
				
			} else {
				pai.direito = aux;
				aux.pai = pai;
				
				vitima.direito = aux.esquerdo;
				if(vitima.direito != null)
					vitima.direito.pai = vitima;
				
				aux.esquerdo = vitima;
				vitima.pai = aux;							
			}			
		}
		// Se o pai de aux for raiz...
		else {
			root = aux;
			aux.pai = pai; // null
			
			vitima.direito = aux.esquerdo;
			if(vitima.direito != null)
				vitima.direito.pai = vitima;
			
			aux.esquerdo = vitima;
			vitima.pai = aux;
		}
	} // Zag
	
	/*
	 *  ============= Zig-Zag ===============
	 */
	public void zigZag (Node aux) {
		zig (aux);
		zag (aux);
	}

	/*
	 *  ============= Zag-Zig ===============
	 */
	public void zagZig (Node aux) {
		zag(aux);
		zig(aux);
	}
	
	/*
	 *  ============= Zig-Zig ===============
	 */
	public void zigZig (Node aux) {
		Node bisavo = aux.pai.pai.pai;
		Node avo = aux.pai.pai;
		Node pai = aux.pai;
		if (avo != root) {
			if (avo == bisavo.esquerdo)
				bisavo.esquerdo = aux;
			else 
				bisavo.direito = aux;
			
			aux.pai = bisavo;
				
			avo.esquerdo = pai.direito;
			if(avo.esquerdo != null)
				avo.esquerdo.pai = avo;
			pai.direito = avo;
			avo.pai = pai;
			
			pai.esquerdo = aux.direito;
			if (pai.esquerdo != null)
				pai.esquerdo.pai = pai;
			aux.direito = pai;
			pai.pai = aux;
		}
		// Se avo for raiz....
		else {
			root = aux;
			aux.pai = bisavo; // null
			
			avo.esquerdo = pai.direito;
			if(avo.esquerdo != null)
				avo.esquerdo.pai = avo;
			pai.direito = avo;
			avo.pai = pai;
			
			pai.esquerdo = aux.direito;
			if (pai.esquerdo != null)
				pai.esquerdo.pai = pai;
			aux.direito = pai;
			pai.pai = aux;
		}
	}
	
	/*
	 *  ============= Zag-Zag ===============
	 */
	public void zagZag (Node aux) {
		Node bisavo = aux.pai.pai.pai;
		Node avo = aux.pai.pai;
		Node pai = aux.pai;
		if (avo != root) {
			if (avo == bisavo.esquerdo)
				bisavo.esquerdo = aux;
			else 
				bisavo.direito = aux;
			
			aux.pai = bisavo;
				
			avo.direito = pai.esquerdo;
			if(avo.direito != null)
				avo.direito.pai = avo;
			pai.esquerdo = avo;
			avo.pai = pai;
			
			pai.direito = aux.esquerdo;
			if (pai.direito != null)
				pai.direito.pai = pai;
			aux.esquerdo = pai;
			pai.pai = aux;
		}
		// Se avo for raiz....
		else {
			root = aux;
			aux.pai = bisavo;
			
			avo.direito = pai.esquerdo;
			if(avo.direito != null)
				avo.direito.pai = avo;
			pai.esquerdo = avo;
			avo.pai = pai;
			
			pai.direito = aux.esquerdo;
			if (pai.direito != null)
				pai.direito.pai = pai;
			aux.esquerdo = pai;
			pai.pai = aux;
		}
	}
	
	/*
	 * ============= Gerenciador de Rotações =============== 
	 */
	public void gerRotacao (Node aux) { // Gerencia as Rotações de modo a levar o elemento à raiz!
		if (aux == root) {
			return;
		}
		// Zig e Zag
		else if (aux.pai == root) {
			if(aux.getNumero() < aux.pai.getNumero ())
				zig (aux);
			else
				zag (aux);
		} 
		// Zig-Zig; Zig-Zag; Zag-Zag e Zag-Zig
		else {
			if (aux == aux.pai.esquerdo && aux.pai == (aux.pai.pai).direito)
				zigZag (aux);
			else if (aux == aux.pai.direito && aux.pai == (aux.pai.pai).esquerdo)
				zagZig (aux);
			else if (aux == aux.pai.esquerdo && aux.pai == (aux.pai.pai).esquerdo)
				zigZig (aux);
			else
				zagZag (aux);
		}
		gerRotacao (aux);
	}
	/********************************************************************************************************
	 ************************************** FUNÇÃO VAZIA ****************************************************
	 ********************************************************************************************************/
	public boolean vazia () { return root == null; }
	
	/********************************************************************************************************
	 ************************************* FUNÇÕES DE INSERÇÃO **********************************************
	 ********************************************************************************************************/
	public void inserirAPartirDaRaiz (int n) {
		inserir(n, 0, 0, DELTA, null, root);
	}
	// :::::::::::::::::::Função Inserir::::::::::::::::::::
	public void inserir(int n,int posx, int posy, int delta, Node novo, Node aux) {
		
		if(aux != null) // Não permite que se coloque número ja contidos na arvore
			if(aux.getNumero() == n)
				return;
		
		if(delta < 15)	// limita o delta a fica maior que 18
			delta = 15;
		if (novo == null) {
			novo = new Node(n);
		}
		if(vazia()) {
			root = novo;
			root.setPosition ((painel_width/2) - root.getWidth()/2, 30);
			root.pai = null;
			this.add(root);
			return;
		}
		boolean
			cond1 = (aux.getNumero() < n && aux.direito == null ),
			cond2 = (aux.getNumero() < n && aux.direito != null),
			cond3 = (aux.getNumero() > n && aux.esquerdo == null);
		
		if(cond1) {
			aux.direito = novo;
			(aux.direito).pai = aux;
			(aux.direito).setPosition(aux.x + delta, aux.y + 60);
			this.add(aux.direito);	
			// Inserir Linha.
			aux.l_direita = new Linha(aux.x, aux.y, aux.direito.x, aux.direito.y, false);
			add(aux.l_direita);
		}
		else if(cond2) {
			inserir(n, aux.x, aux.y, (6*delta)/11 , novo, aux.direito);
		}else if(cond3) {
			aux.esquerdo = novo;
			aux.esquerdo.pai = aux;
			aux.esquerdo.setPosition (aux.x - delta, aux.y + 60);
			this.add(aux.esquerdo);
			//Insere linha
			aux.l_esquerda = new Linha(aux.x, aux.y, aux.esquerdo.x, aux.esquerdo.y, true);
			add(aux.l_esquerda);
		
		}else {
			inserir(n, aux.x, aux.y, (6*delta)/11, novo, aux.esquerdo);
		}
		
	} // Inserir
	/********************************************************************************************************
	 **************************************FUNÇÃO DE REPOSICIONAMENTO****************************************
	 ********************************************************************************************************/
	public void reposicione(int x, int y, int delta, Node aux) {
		remove(aux);
		aux.setPosition(x, y);
		add(aux);	
		//Recursão
		if (aux.direito != null)
			reposicione (aux.x + delta, aux.y + 60, (6*delta)/11, aux.direito);
		if (aux.esquerdo != null)
			reposicione (aux.x - delta, aux.y + 60, (6*delta)/11, aux.esquerdo);
		
		//Trabalho com linhas
		if(aux.l_direita != null)
			remove(aux.l_direita);
		if(aux.l_esquerda != null)
			remove(aux.l_esquerda);
		if(aux.direito != null){
			aux.l_direita = new Linha(aux.x, aux.y, aux.direito.x, aux.direito.y, false);
			add(aux.l_direita);
		}
		if(aux.esquerdo != null){
			aux.l_esquerda = new Linha(aux.x, aux.y, aux.esquerdo.x, aux.esquerdo.y, true);
			add(aux.l_esquerda);
		}
	} // Reposicione
	
	/********************************************************************************************************
	 **************************************FUNÇÕES DE BUSCA**************************************************
	 ********************************************************************************************************/
	public void buscaComRotacao (int n) {
		if (root == null)
			return;
		
		Node aux = busca (n, root);
		if (aux != null) {
		gerRotacao (aux);
		reposicione ((painel_width/2) - root.getWidth()/2, 30, DELTA, root);
		buscado.setText("Elemento Buscado: "+n);
		}else {
			buscado.setText("Nenhum elemento encontrado!");
		}
	} // Busca_com_Rotacao
	
	public Node busca (int n, Node aux) {
		
		if(n == aux.getNumero())
			return aux;
		else if(n > aux.getNumero() && aux.direito != null)
			return busca(n, aux.direito);
		else if(n < aux.getNumero() && aux.esquerdo != null)
			return busca(n, aux.esquerdo);
		return null;
	} // Busca
	
	/********************************************************************************************************
	 **************************************FUNÇÕES DE REMOÇÃO************************************************
	 ********************************************************************************************************/
	
	public void remover (int n) {
		Node aux = busca (n, root);
		
		if (aux == null)
			return;
		
		//Caso Especial - Raiz -
		if (aux == root) {
			if (aux.esquerdo == null && aux.direito == null) {
				root = null;
			}
			else if(altura(aux.direito) >= altura(aux.esquerdo)) {
				root = aux.direito;
				aux.direito.pai = null;
				
				// Procura um lugar vazio a esquerda de aux.esquerdo.
				Node aux2 = aux.direito;
				if(aux.esquerdo != null){
					while (aux2.esquerdo != null)
						aux2 = aux2.esquerdo;
					
					aux2.esquerdo = aux.esquerdo;
					aux2.esquerdo.pai = aux2;
					
					
				}	
				reposicione(aux.x, aux.y, DELTA, aux.direito);
			}else if(altura(aux.esquerdo) > altura(aux.direito)) {
				root = aux.esquerdo;
				aux.esquerdo.pai = null;
				
				// Procura um lugar vazio a direita de aux.direito
				if(aux.direito != null ) {
					Node aux2 = aux.esquerdo;
					while (aux2.direito != null)
						aux2 = aux2.direito;
					
					aux2.direito = aux.direito;
					aux2.direito.pai = aux2;
				}
				reposicione(aux.x, aux.y, DELTA, aux.esquerdo);
			}
			remove(aux);
			if(aux.l_direita != null)
				remove(aux.l_direita);
			if(aux.l_esquerda != null)
				remove(aux.l_esquerda);
			return;
		}
		// ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
		// :::::::::::::::: Caso o Elemento a ser Removido não seja root:::::::::::::
		// ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
		int delta = aux.pai.x - aux.x; // distancia horizontal entre o pai do elemento a ser removido e ele.
		if(delta < 0) // distancia nao pode ser negativo.
			delta = -delta;
		
		// Caso ele esteja a direita do pai dele
		if(aux.pai.direito == aux) {	
			
			if (aux.esquerdo == null && aux.direito == null) {
				aux.pai.direito = null;
			}
			else if(altura(aux.esquerdo) <= altura(aux.direito)) {
				aux.pai.direito = aux.direito;
				aux.direito.pai = aux.pai;
				
				// Procura um lugar vazio a esquerda de aux.esquerdo.
				Node aux2 = aux.direito;
				if(aux.esquerdo != null){
					while (aux2.esquerdo != null)
						aux2 = aux2.esquerdo;
					aux2.esquerdo = aux.esquerdo;
					aux2.esquerdo.pai = aux2;
				}				
			}else{
				aux.pai.direito = aux.esquerdo;
				aux.esquerdo.pai = aux.pai;
				
				// Procura um lugar vazio a direita de aux.direito
				if(aux.direito != null ) {
					Node aux2 = aux.esquerdo;
					while (aux2.direito != null)
						aux2 = aux2.direito;
					aux2.direito = aux.direito;
					aux2.direito.pai = aux2;
				}
			}
		}
		// Caso o elemento a ser removido seja Filho esquerdo do pai dele!
		else {
			if (aux.esquerdo == null && aux.direito == null) {
				aux.pai.esquerdo = null;
			}
			// Se a Altura do filho direito do elemento for
			// maior que a do esquerdo o elemento direito ficará
			// no lugar do elemento a ser removido
			else if(altura(aux.esquerdo) <= altura(aux.direito)) {
				aux.pai.esquerdo = aux.direito;
				aux.direito.pai = aux.pai;
				
				// Procura um lugar vazio a esquerda de aux.esquerdo.
				Node aux2 = aux.direito;
				if(aux.esquerdo != null){
					while (aux2.esquerdo != null)
						aux2 = aux2.esquerdo;
					aux2.esquerdo = aux.esquerdo;
					aux2.esquerdo.pai = aux2;
				}	
				
			}
			// Se for o contrário
			// o elemento esquerdo ficara no lugar
			// do elemento a ser removido
			else {
				aux.pai.esquerdo = aux.esquerdo;
				aux.esquerdo.pai = aux.pai;
				
				// Procura um lugar vazio a direita de aux.direito
				if(aux.direito != null ) {
					Node aux2 = aux.esquerdo;
					while (aux2.direito != null)
						aux2 = aux2.direito;
					aux2.direito = aux.direito;
					aux2.direito.pai = aux2;
				}
			}
		}
		// Remove Elemento da interface
		remove(aux);
		//removendo linhas
		if(aux.l_direita != null)
			remove(aux.l_direita);
		if(aux.l_esquerda != null)
			remove(aux.l_esquerda);
		
		// Faz o reposicionamento dos elementos
		reposicione((painel_width/2) - root.getWidth()/2, 30, DELTA, root);
	} // Remover

}	
	


